Overlay networks permit designers to implement customized routing and packet management algorithms on top of the Internet. Overlays use Internet paths between end-hosts as links upon which the overlay routing information, building a network on top of the network. Routing and storage and lookup overlays have become a substrate upon which a number of large distributed systems are based. For example, many peer-to-peer (P2P) systems have in overlay network at their core, presenting a hash-table-like “get (key)/set (key, value)” interface. Such overlays are structured and called distributed hash tables (DHTs). In other words, DHTs represent a class of decentralized distributed systems that partition ownership of a set of keys among participating nodes in a network. DHTs are used by the network nodes to route messages (e.g., queries) to the unique owner of any given key. There is one basic operation in DHT systems, lookup (key), which returns the identity (e.g., the IP address) of the node storing an object with that key. This enables nodes to insert, retrieve, and delete data items based on their respective key. State of the art DHT-based P2P system designs typically achieved key lookup at O(logN) complexity with each node maintains O(logN) states of other nodes.
DHTs can directly support only exact-match lookups (i.e. queries). As a result, DHT search operations are substantially limited. For instance, a range query, which is a query to find all objects associated with keys in a certain range over an underlying P2P network (i.e., a range query asks for all objects with values in a certain range), is difficult to directly achieve via DHT lookup. This is because a cryptographic hash function (e.g., SHA hash) strips the structural properties on keys to distribute keys uniformly. As a result, ordering among keys is not reliable.